## python 3.9.13
#%%
import random

#%%[markdown]
"""
### 程序设计题: 单链表实验
1. 从键盘输入若干大于0的整数，用这些整数构造一个单链表.当用户输入小于等于0的值时，创建链表结束并在终端打印输出这个链表。
2. 在链表中查找某结点，如果能找到输出这个结点是第几个结点，如果找不到，输出:找不到此结点。
3. 删除指定结点: 如果指定的被删除结点存在就删除它,然后打印：已经删除，如果不存在，输出信息：链表中没有此结点，无法删除。
4. 删除重复结点：如果链表中有重复的元素，删除重复的元素，使得所有值最多只出现一次，例如，如果链表中有3个结点的值是100，那么需要删除两个值为100的结点。只保留一个值为100的结点。删除重复结点后打印输出整个链表
"""

#%%
class Nodes(object):
    """
    使用python中的类代替C++中的结构体,创建链表中节点
    + Curr::链表中的当前值
    + Next::链表中后续节点
    """

    Curr = None
    Next = None


#%%
class Chain(object):
    """
    构建链表
    """

    def __init__(self):
        """
        初始化类元素,
        + self.data::私有变量,用于存储节点信息
        + self.size::链表元素总数
        """
        self.data = None
        self.size: int = 0

    def addNode(self, Data):
        """
        采用头插法创建链表,
        + Data::输入数据项
        """
        NewNode = Nodes()
        NewNode.Curr = Data
        NewNode.Next = self.data
        self.data = NewNode
        self.size += 1

    def CreateChain(self) -> str:
        """
        构建手动输入用的函数,
        函数内调用self.addNode(),
        将数据插入值链表中.
        + return::调用self.Display()
        """
        info = "请输入一个数值\n小于零结束输入"
        print(info)
        while True:
            data = input("请输入:")  # 输入需要添加至链表中的参数
            if "-" in data:  # 判断是否包含 -,如果包含且其余所有值为整形,则退出输入
                if data.replace("-", "").isdigit():
                    return self.Display()
            elif data.isdigit():  # 如果是数值,且为正则继续插入
                data = int(data)
                if data >= 0:
                    self.addNode(data)
            else:
                print(info)

    def Display(self):
        """
        用于展示当前链表情况
        """
        cursor = self.data  # 构建指针
        s = ""
        c = 0
        while cursor:
            s += "{}->".format(cursor.Curr)  # 将输出值拼接至字符串中, 相当于 s + cursor.Curr + '->'
            cursor = cursor.Next  # 循环节中将指针指向下一个节点
            c += 1
        return s[
            :-2
        ]  # 将最后的 -> 截断后输出 4->5->5->5->3->0->4-> 取除最后一个箭头,值输出 4->5->5->5->3->0->4

    def SearchByValue(self, searchValue: int) -> str:
        """
        按值搜索,
        + searchValue::需要搜索的值
        """
        cursor = self.data  # 创建指针
        ind = 0
        while cursor:
            if cursor.Curr == searchValue:  # 如果指针值与搜索值一致,则返回索引和值
                return "node#:{} | value:{}".format(ind, cursor.Curr)
            cursor = cursor.Next
            ind += 1
        return "找不到此结点"  # 遍历结束后如果依然无法找到,则返回无法找到

    def SearchByIndex(self, indexNumber: int) -> str:
        """
        按索引搜索值
        + indexNumber::索引值
        """
        if self.size <= indexNumber:  # 如果输入的索引大于当前链表长度,直接退出
            return "index out of bound"
        cursor = self.data  # 创建指针
        for _ in range(indexNumber):
            cursor = cursor.Next  # 将指针向后移动 n 次
        return "node#:{} | value:{}".format(indexNumber, cursor.Curr)

    def DeleteNodeByValue(self, searchValue: int) -> str:
        """
        按照值搜索,并删除与搜索值一致的第一个节点
        + searchValue 搜索值
        """
        cursor = self.data  # 创建指针
        if cursor.Curr == searchValue:  # 当指针与头指针一致时
            tmp = cursor.Next
            self.data = tmp  # 数据等于链表头.next
        else:
            while cursor:  # 否则循环链表,并偏移指针
                if cursor.Next is None:  # 如果后一个指针为空,则代表链表已经到末尾
                    return "{} not in data ".format(searchValue) + "链表中没有此结点，无法删除"
                elif cursor.Next.Curr == searchValue:
                    tmp = cursor.Next.Next  # 临时存储指针
                    cursor.Next = tmp  # 斌将指针的Next指向 next.next
                    break
                cursor = cursor.Next  # 否则向后偏移一个指针
        self.size -= 1
        return "{} is now del from data 已经删除".format(searchValue)

    def DropDuplicat(self) -> str:
        """
        取除重复值
        """
        cursorA = self.data  # 创建指针A
        while cursorA:
            cursorB = cursorA  # 创建指针B,并赋予与指针A相同的节点
            while cursorB:
                if cursorB.Next:  # 如果指针B.Next为空,则循环结束
                    if cursorA.Curr == cursorB.Next.Curr:
                        tmp = cursorB.Next.Next  # 临时存储指针值
                        cursorB.Next = tmp  # 将指针B.next 指向 B.next.next
                        self.size -= 1
                    else:
                        cursorB = cursorB.Next  # 指针向后偏移一项
                else:
                    break
            cursorA = cursorA.Next
        return self.Display()


#%%
if __name__ == "__main__":
    n = 20  # 随机数数量
    NewChain = Chain()  # 初始化链表
    print(NewChain.CreateChain())  # 手都输入测试
    #%%
    dataList = [random.randint(0, int(n / 4)) for i in range(n)]  # 创建随机数构成的列表,用于测试
    for i in dataList:
        NewChain.addNode(i)  # 将随机数输入至链表中
    print(NewChain.size, NewChain.Display(), "\n")
    #%%
    print(NewChain.SearchByValue(n * 20))  # 搜索用例1 搜索不存在的值
    print(NewChain.SearchByValue(dataList[5]))  # 搜索用例2 搜索列表中存在的至
    print(NewChain.SearchByIndex(n + 10))  # 索引搜索用例1 搜索超出索引的值
    print(NewChain.SearchByIndex(int(n / 2)))  # 索引搜索用例2 搜索索引可以查询到的值
    #%%
    print(NewChain.size, NewChain.Display())
    print(NewChain.DeleteNodeByValue(dataList[5]), "\n")  # 删除列表中存在的值
    print(NewChain.size, NewChain.Display())
    print(NewChain.DeleteNodeByValue(dataList[0]), "\n")  # 删除首节点值
    print(NewChain.size, NewChain.Display())
    print(NewChain.DeleteNodeByValue(n * 10))  # 删除一个不存在的值
    #%%
    print(NewChain.size, NewChain.Display(), "\n")
    print(NewChain.size, NewChain.DropDuplicat())  # 删除重复值
    for i in [n * 10] * 20:  # 添加重复值值链表中
        NewChain.addNode(i)
    print(NewChain.size, NewChain.Display())
    print(NewChain.size, NewChain.DropDuplicat())  # 测试是否取除重复值
    print("测试结束")
#%%
